// Author : Zhuowen Tu


#include "mcmcBlock.h"


// construction & destruction
BoundCode::BoundCode()
{
	y = 0.0;
	bShowOn = true;
}

BoundCode::~BoundCode()
{
}

// operators
BoundCode&	BoundCode::operator=(const BoundCode &x)
{
	if (&x==this)
		return *this;
	else
	{
		y = x.y;
		bShowOn = x.bShowOn;
		return *this;
	}
}

bool BoundCode::operator==(const BoundCode& x)
{
	if (y==x.y)
		return true;
	else
		return false;
}

bool BoundCode::operator<=(const BoundCode& x)
{
	if (y<=x.y)
		return true;
	else
		return false;
}

bool BoundCode::operator<(const BoundCode& x)
{
	if (y<x.y)
		return true;
	else
		return false;
}

bool operator<(const BoundCode &x1, const BoundCode &x2)
{
	if (x1.y<x2.y)
		return true;
	else
		return false;
}

bool BoundCode::operator>=(const BoundCode& x)
{
	if (y>=x.y)
		return true;
	else
		return false;
}
bool BoundCode::operator>(const BoundCode& x)
{
	if (y>x.y)
		return true;
	else
		return false;
}

// construction & destruction
MCMC_Boundary::MCMC_Boundary()
{
	points = NULL;
	num_points = 0;
	flag_pixel_on = NULL;
	rect_bound.Set(9999,9999,-9999,-9999);
	next = NULL;
}

MCMC_Boundary::~MCMC_Boundary()
{
	Free();
}

void MCMC_Boundary::Free(void)
{
	if (points != NULL)
		delete []points;
	points = NULL;
	if (flag_pixel_on != NULL)
		delete []flag_pixel_on;
	flag_pixel_on = NULL;
	rect_bound.Set(9999,9999,-9999,-9999);
	next =	NULL;
	num_points = 0;
}

// operations
void MCMC_Boundary::SetPointCount(int size)
{
	if (size > 0)
	{
		Free();
		num_points = size;
		points = new McPoint2D[num_points];
		assert(points != NULL);
		flag_pixel_on = new bool[num_points];
		assert(flag_pixel_on != NULL);
	}
}

void MCMC_Boundary::Set(MCMC_AtomicRegion &region)
{
	int			id_node,size=0,i,id_cseg;
	MCMC_Node	*pnode;
	MCMC_Contour_Segment *pcseg;

	rect_bound.Set(9999,9999,-9999,-9999);
	// find how many nodes exist on the contour
	size = region.NumNodes();
	if (size<=0)
		return;

	// allocate memory
	SetPointCount(size);

	// save coordinates of every node on the boundary
	i = 0;
	id_node = region.GetFirstNode();
	while (id_node >= 0)
	{
		pnode = region.LayerRegion()->GetNode(id_node);
		assert(pnode != NULL);

		points[i].x = IntClose(pnode->GetY())-0.5;
		points[i].y = IntClose(pnode->GetX())-0.5;

		rect_bound.SetBound((int)floor(points[i].x),(int)floor(points[i].y));
		rect_bound.SetBound((int)ceil(points[i].x),(int)ceil(points[i].y));

		id_cseg = region.GetCurrentCSeg();
		pcseg = region.LayerRegion()->GetCSeg(id_cseg);
		if (pcseg != NULL)
			flag_pixel_on[i] = 	pcseg->ShowOnPixel(region.Id(),id_node);
		else
			flag_pixel_on[i] = true;

		i++;
		id_node = region.GetNextNode();
	}
}

void MCMC_Boundary::Set(McPoint2D *p_points, const int num_points)
{
	rect_bound.Set(9999,9999,-9999,-9999);
	if (p_points==NULL || num_points<=0)
		return;

	// allocate memory
	SetPointCount(num_points);

	// save the coordinates
	int	i;

	for (i=0; i<num_points; i++)
	{
		points[i].x = IntClose(p_points[i].GetY())-0.5;
		points[i].y = IntClose(p_points[i].GetX())-0.5;

		rect_bound.SetBound((int)floor(points[i].x),(int)floor(points[i].y));
		rect_bound.SetBound((int)ceil(points[i].x),(int)ceil(points[i].y));
		flag_pixel_on[i] = true;
	}
}


void MCMC_Boundary::Set(MCMC_Layer_Regions &graph, LinkList<int> &list_ver,LinkList<int> &list_cseg)
{
	int						id_ver,i,id_cseg,id_node,direction;
	bool					bGo1,bGo2;
	MCMC_Vertex				*pver;
	MCMC_Contour_Segment	*pcseg;
	MCMC_Node				*pnode;
	LinkList<McPoint2D>		list_nodes;
	McPoint2D				pt2d;

	rect_bound.Set(9999,9999,-9999,-9999);
	bGo1 = list_ver.GetFirst(id_ver);
	bGo2 = list_cseg.GetFirst(id_cseg);
	while (bGo1 && bGo2)
	{
		pver = graph.GetVertex(id_ver);
		assert(pver != NULL);
		pcseg = graph.GetCSeg(id_cseg);
		assert(pcseg != NULL);

		if (id_ver==pcseg->end[0])
			direction = 0;
		else
		{
			assert(id_ver==pcseg->end[1]);
			direction = 1;
		}

		if (direction==0)
			id_node = pcseg->GetFirstNode();
		else
			id_node = pcseg->GetLastNode();
		while (id_node>=0)
		{
			pnode = graph.GetNode(id_node);
			assert(pnode != NULL);

			pt2d.x = IntClose(pnode->GetY())-0.5;
			pt2d.y = IntClose(pnode->GetX())-0.5;

			rect_bound.SetBound((int)floor(pt2d.x),(int)floor(pt2d.y));
			rect_bound.SetBound((int)ceil(pt2d.x),(int)ceil(pt2d.y));

			list_nodes.Insert(pt2d);

			if (direction==0)
				id_node = pcseg->GetNextNode();
			else
				id_node = pcseg->GetPrevNode();
		}

		bGo1 = list_ver.GetNext(id_ver);
		bGo2 = list_cseg.GetNext(id_cseg);
	}

	SetPointCount(list_nodes.Num());
	i=0;
	bGo1 = list_nodes.GetFirst(pt2d);
	while (bGo1)
	{
		points[i].x = pt2d.x;
		points[i].y = pt2d.y;

		bGo1 = list_nodes.GetNext(pt2d);
		i++;
	}
}


void MCMC_Boundary::Intersection(MinHeap<BoundCode> &heap, const McPoint2D &dp2d1, const McPoint2D &dp2d2)
{
	int			i,result;
	McPoint2D	pt2d_new;
	BoundCode	y_ins;

	for (i=0; i<num_points; i++)
	{
		// compute the intersection of two stragiht line segments
		result = LineIntersection(&pt2d_new, points[i],points[(i+1)%num_points],dp2d1, dp2d2);
		if (result == CROSSING)
		{
			y_ins.Set(pt2d_new.y,flag_pixel_on[i]);
			if (Distance(pt2d_new,points[(i+1)%num_points])>EBSHLON)
				heap.Insert(y_ins);
		}
	}
}

double MCMC_Boundary::Area(void)
{
	darea = 0.0;

	if (num_points<3)
		return darea;
	else
	{
		int		i;

		for (i=0; i<num_points; i++)
			darea += points[i].x*(points[(i+num_points-1)%num_points].y-points[(i+1)%num_points].y);
		darea = fabs(darea)/2;
		return darea;
	}
}

//clockwise return 1, counterclockwise return 0
bool MCMC_Boundary::Clockwise(void)
{
	MinHeap<BoundCode> heap_temp;
	McPoint2D	dp2d1,dp2d2,dp2dNew;
	int			i,cond_pos;
	BoundCode	bc1,bc2;

	// find one point inside the region
	dp2d1.Set(0,-5000);
	dp2d2.Set(0,5000);
	if (num_points<=0)
		return false;
	for (i=0; i<num_points; i++)
	{
		dp2d1.x = points[i].x+0.05;
		dp2d2.x = points[i].x+0.05;

		heap_temp.Empty();
		Intersection(heap_temp,dp2d1,dp2d2);
		if (heap_temp.Size()>=2)
			break;
	}
	if (heap_temp.Size()>=2)
	{
		if (!heap_temp.DeleteMin(bc1))
			return false;
		if (!heap_temp.DeleteMin(bc2))
			return false;
		dp2dNew.Set(dp2d1.x,(bc1.Y()+bc2.Y())/2.);

		// determin the direction
		cond_pos = VeriPoint(points, num_points, dp2dNew.x, dp2dNew.y);
		assert(cond_pos != 0);
	}
	if (cond_pos==INSIDE_CW)
		return true;
	else
		return false;
}


bool MCMC_Boundary::Inside(McPoint2D pt2d)
{
	int position,i;
	if (num_points < 3)
		return false;

	position = VeriPoint(points, num_points, pt2d.x, pt2d.y);
	if (position == 0)
		return false;
	else
	{
		for (i=0; i<num_points; i++)
			if (pt2d == points[i])
				return false;
		return true;
	}
}

/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
// construction & destruction
MCMC_Block::MCMC_Block()
{
	pheap = new MinHeap<BoundCode>(500);
	pboundary_outer = NULL;
}

MCMC_Block::~MCMC_Block()
{
	if (pheap!=NULL)
		delete pheap;
	pheap = NULL;

	Free();
}

void MCMC_Block::Free(void)
{
	MCMC_Boundary	*pmove;

	while (pboundary_outer!=NULL)
	{
		pmove = pboundary_outer;
		pboundary_outer = pboundary_outer->next;
		delete pmove;
	}
}

void MCMC_Block::EmptyHeap(void)
{
	if (pheap != NULL)
		pheap->Empty();
}

// operations
void MCMC_Block::Set(MCMC_AtomicRegion &region)
{
	MCMC_Boundary	*pboundary,*pmove;
	int				id_region_hole;
	MCMC_AtomicRegion		*pregion_hole;

	// free allocated memory
	Free();

	pboundary = new MCMC_Boundary();
	assert (pboundary != NULL);

	// find the bounding box
	rect_bound.Set(9999,9999,-9999,-9999);

	pboundary->Set(region);
	rect_bound.SetBound(pboundary->rect_bound.left, pboundary->rect_bound.top);
	rect_bound.SetBound(pboundary->rect_bound.right, pboundary->rect_bound.bottom);

	pboundary_outer = pboundary;
	pmove = pboundary_outer;

	// get all the holes
	id_region_hole = region.GetFirstHole();
	while (id_region_hole >= 0)
	{
		pregion_hole = region.LayerRegion()->GetAtomicRegion(id_region_hole);
		assert(pregion_hole != NULL);

		pboundary = new MCMC_Boundary();
		assert (pboundary != NULL);

		pboundary->Set(*pregion_hole);
		rect_bound.SetBound(pboundary->rect_bound.left, pboundary->rect_bound.top);
		rect_bound.SetBound(pboundary->rect_bound.right, pboundary->rect_bound.bottom);

		pmove->next = pboundary;
		pmove = pboundary;

		// get next hole
		id_region_hole = region.GetNextHole();
	}
}

int MCMC_Block::Label(MCMC_AtomicRegion &region, mcmcMatrix<int> &image, const int id_label)
{
	// initialization
	Set(region);

	MCMC_Boundary	*pmove;
	double			x,y,mean=0.0;
	McPoint2D		pt2d1,pt2d2;
	bool			bGo1,bGo2,bValid;
	int				ys,ye;
	int			count=0;

	BoundCode		bc1,bc2;

	pt2d1.y = -2.0;
	pt2d2.y = 2.0+image.rows();

	// scan-line algorithm
	for (x=(double)pboundary_outer->rect_bound.left-2.0; x<(double)pboundary_outer->rect_bound.right+2.0; x=x+1.0)
	{
		pt2d1.x = x;
		pt2d2.x = x;
		// free heap members
		EmptyHeap();

		pmove = pboundary_outer;
		while (pmove != NULL)
		{
			// compute intersection
			pmove->Intersection(*pheap,pt2d1,pt2d2);
			pmove = pmove->next;
		}

		bGo1 = pheap->DeleteMin(bc1);
		bGo2 = pheap->DeleteMin(bc2);
		bValid = true;
		while (bGo2)
		{
			ys = (int)(bc1.Y()-1.0);
			ye = (int)(bc2.Y()+1.0);
			if (bValid)
			{
				for (y=(double)ys; y<=(double)ye; y=y+1.0)
				{
					if (y>=bc1.Y()-EBSHLON && y<=bc2.Y()+EBSHLON)
					{
						if (image.Valid((int)y,(int)x))
						{
							image((int)y,(int)x) = id_label;
							count++;
						}
					}
				}
			}
			bValid = !bValid;
			// get the next intersection
			bc1 = bc2;
			bGo2 = pheap->DeleteMin(bc2);
		}
	}
	return count;
}

void MCMC_Block::LabelToPixelSet(MCMC_AtomicRegion &region, MCMC_PixelSet &pixel_set)
{
	// initialization
	Set(region);

	MCMC_Boundary	*pmove;
	double			x,y,mean=0.0;
	McPoint2D		pt2d1,pt2d2;
	bool			bGo1,bGo2,bValid;
	int				ys,ye,row,col;
	int			count=0;

	BoundCode		bc1,bc2;

	pt2d1.y = -2.0;
	pt2d2.y = 2.0+rect_bound.bottom;

	// scan-line algorithm
	for (x=(double)pboundary_outer->rect_bound.left-2.0; x<(double)pboundary_outer->rect_bound.right+2.0; x=x+1.0)
	{
		pt2d1.x = x;
		pt2d2.x = x;
		// free heap members
		EmptyHeap();

		pmove = pboundary_outer;
		while (pmove != NULL)
		{
			// compute intersection
			pmove->Intersection(*pheap,pt2d1,pt2d2);
			pmove = pmove->next;
		}

		bGo1 = pheap->DeleteMin(bc1);
		bGo2 = pheap->DeleteMin(bc2);
		bValid = true;
		while (bGo2)
		{
			ys = (int)(bc1.Y()-1.0);
			ye = (int)(bc2.Y()+1.0);
			if (bValid)
			{
				for (y=(double)ys; y<=(double)ye; y=y+1.0)
				{
					if (y>=bc1.Y()-EBSHLON && y<=bc2.Y()+EBSHLON)
					{
						row = (int)y;
						col = (int)x;
						pixel_set.Insert(row, col);
					}
				}
			}
			bValid = !bValid;
			// get the next intersection
			bc1 = bc2;
			bGo2 = pheap->DeleteMin(bc2);
		}
	}
}

// construction & destruction
MCMC_Grid_Index::MCMC_Grid_Index()
{
	height = 0.0;
	width  = 0.0;
	pindex = NULL;
	num_region = 0;
}

MCMC_Grid_Index::~MCMC_Grid_Index()
{
	if (pindex != NULL)
		delete []pindex;
	pindex = NULL;
}

void MCMC_Grid_Index::Set(const double dheight, const double dwidth, const int num)
{
	height	= dheight;
	dh		= height/MI_GRID_SIZE;
	width	= dwidth;
	dw		= width/MI_GRID_SIZE;
	num_region = num;
	if (pindex != NULL)
		delete []pindex;
	pindex = new int[num_region];
}

int MCMC_Grid_Index::GetIndex(const double x, const double y)
{
	double	row,col;
	int		j,i;

	row = x/dh;
	col = y/dw;

	// left-top
	j = (int)floor(row);
	i = (int)floor(col);
	if (j<0)				j=0;
	if (j>=MI_GRID_SIZE)	j=MI_GRID_SIZE-1;
	if (i<0)				i=0;
	if (i>=MI_GRID_SIZE)	i=MI_GRID_SIZE-1;

	return j*MI_GRID_SIZE+i;
}

int MCMC_Grid_Index::Add(const irmm_Rect &rect, const int j)
{
	double	x[4],y[4];
	int		index[4],i;
	bool	bOut;
	int		temp=j;

	// set the coordinates of the four corners
	x[0] = (double)rect.top;	y[0] = (double)rect.left;
	x[1] = (double)rect.top;	y[1] = (double)rect.right;
	x[2] = (double)rect.bottom; y[2] = (double)rect.left;
	x[3] = (double)rect.bottom; y[3] = (double)rect.right;

	bOut = false;
	index[0] = GetIndex(x[0], y[0]);
	for (i=1; i<4; i++)
	{
		index[i] = GetIndex(x[i],y[i]);
		if (index[i] != index[0])
		{
			bOut = true;
			break;
		}
	}
	if (bOut)
	{
		list_addtional.Insert(temp);
		pindex[j] = -1;
	}
	else
	{
		int temp=j;
		pIndex_list[index[0]].Insert(temp);
		pindex[j] = index[0];
	}
	return pindex[j];
}

int MCMC_Grid_Index::GetGridIndex(const int j)
{
	assert(j>=0 && j<num_region);
	return pindex[j];
}
